"""
堆栈
"""
class HeapQueue:
    def swap(self,nums:list,i1:int,i2:int):
        tmp=nums[i1]
        nums[i1]=nums[i2]
        nums[i2]=tmp

    def heapAdjust(self, nums: [int], index: int, end: int):
        """
        将完全二叉树调整为二叉堆(此方法应当从后向前执行)
        nums:原始数组
        index:开始调整的索引
        end:结束位置
        :return:
        """
        while True:
            left=index*2+1
            right=left+1
            if left>=end:
                break
            max_index=index
            # if nums[index]

        pass

    def heapify(self, nums: [int]):
        """
        将数组构建为二叉堆方法（初始堆建立方法）
        :return:
        """
        pass


    def heappush(self, nums: list, value):
        """
        向堆中添加元素，也是优先队列的入队操作
        :return:
        """
        nums.append(value)

        i=len(nums)-1
        while True:
            pi=(i-1)//2
            if pi>=0 and nums[pi]<nums[i]:
                self.swap(nums,pi,i)
                i=pi
            else:
                break

        pass

    def heappop(self, nums: list)->int:
        """
        删除堆顶元素，也是优先队列的出队操作，弹出优先队列中优先级最高的元素
        :return:
        """
        if len(nums) == 0:
            raise Exception('nums is empty')

        result=nums[0]
        top=0
        while True:
            left=top*2+1
            right=left+1
            if left>= len(nums):
                break
            elif right==len(nums) or nums[left]>nums[right]:
                self.swap(nums,top,left)
                top=left
            else:
                self.swap(nums,top,right)
                top=right

        pass
        return result


    def heapsort(self, nums: [int]):
        """
        堆排序
        :return:
        """
        pass

if __name__ == '__main__':
    pass